package course.p2_recursion;

import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 分治策略递归学习
 */
public class RecursionStudy {

    /**
     * 递归实现，阶乘算法
     * @param n
     * @return
     */
    static int jieCheng(int n){
        if(n==0) return 1;
        if(n>0){
            return jieCheng(n-1)*n;
        }
        return jieCheng(n+1)*n;
    }

    @Test
    public void jieChengTest(){
        System.out.println("-10--10的阶乘排列如下：");
        for(int i=-10;i<=10;i++) {
            System.out.print(jieCheng(i)+" ");
        }
    }

    /**
     * 斐波那契数
     * 问题描述：给出一个数，求出它的斐波那契数
     * 1，1，2，3，5，8，13是一个斐波那契数列，当n=5时，它的斐波那契数为8，依次类推。
     * 其公式定义为：
     * n<=1时, F(n)=1
     * n>1时,  F(n)=F(n-1)+F(n-2)
     * @param n
     * @return
     */
    public static int fib(int n) {
        if(n<0) {
            System.out.println("错误输入");
            return -1;
        }
        if(n<=1)
            return 1;
        else
            return fib(n-1)+fib(n-2);
    }

    /**
     * 斐波那契数的动态规划解法
     * @param n
     * @return
     */
    public static int fib2(int n) {
        if(n<0) {
            System.out.println("错误输入");
            return -1;
        }
        if(n<=1) return 1;
        int[] f = new int[n+1];
        f[0] = 1;
        f[1] = 1;
        for(int i=2;i<=n;i++) {
            f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    }

    @Test
    public void FibTest() {
        System.out.println("-10--10的斐波那契数排列如下:");
        for(int i=-10;i<11;i++){
            //System.out.print(Fib(i)+" ");
            System.out.println(fib2(i)+" ");
        }
    }


    /**
     * 全排列问题计算方法
     * @param a 目标数组
     * @param start r1 起始位置坐标
     * @param end rn 终止位置坐标
     */
    public static void allPermutation(int[] a, int start, int end, List<List<Integer>> result) {
        //递归终止条件
        if (start == end) {
            result.add(Arrays.stream(a).boxed().collect(Collectors.toList()));
        }
        for (int i = start; i <= end; i++) {
            // 过滤掉重复的排列结果
            if (!notEqual(a, start, i)) continue;
            swap(a, start, i);
            allPermutation(a, start + 1, end, result);
            swap(a, start, i);
        }
    }

    /**
     * 交换函数，交换数组a中坐标cursor和i的两个元素
     *
     * @param a      目标数组
     * @param cursor 坐标cursor
     * @param i      坐标i
     */
    public static void swap(int[] a, int cursor, int i) {
        //System.out.print("交换 "+a[cursor]+" "+a[i]);
        int temp = a[cursor];
        a[cursor] = a[i];
        a[i] = temp;
        //System.out.println("为："+a[cursor]+" "+a[i]);
    }

    /**
     * 判断坐标cursor到i-1位置的元素是否等于i位置的元素
     * 如果存在，则返回false
     *
     * @param a      目标数组
     * @param cursor 起始坐标
     * @param i      终止坐标
     * @return 相等false
     */
    public static boolean notEqual(int[] a, int cursor, int i) {
        for (int j = cursor; j < i; j++) {
            if (a[j] == a[i]) {
                //System.out.println(a[j]+"=="+a[i]+"跳过重复结果");
                return false;
            }
        }
        return true;
    }

    @Test
    public void allPermutationTest() {
        int[] nums = {1, 2};
        List<List<Integer>> result = new ArrayList();
        allPermutation(nums, 0, nums.length - 1, result);
        System.out.println(result);

    }


    /**
     * 整数划分问题递归解法
     * @param n
     * @param m
     * @return
     */
    public static int intDivision(int n,int m){
        if(n<1||m<1) return 0;
        if(n==1||m==1) return 1;
        if(n<m) return intDivision(n,n);
        if(n==m) return intDivision(n,m-1)+1;
        return intDivision(n,m-1) + intDivision(n-m,m);
    }
    @Test
    public void intDivisionTest(){
        System.out.println(intDivision(6,6));
    }

}
